For packet processing systems, context data for network packet flows is often required to process network packets. A key, which is often derived from different fields of a packet representing a packet flow, is often associated with this context data. Records including the key and the context data can further be stored within a lookup table for future access and use by the packet processing system. The processing system can further apply an exact match (EM) hash function to the key to generate a primary table index for the record that determines a memory location within a lookup table to store the key and the context data (assuming no collisions). To subsequently read context data from the lookup table, a table index generated from a key associated with an access request is used to determine a memory location within the lookup table, and the record at that location is read. The key associated with the access request is compared to the key within this record to ensure that the correct record has been found in order to perform a read/write operation for the access request. If the key does not match, a collision chain can be followed, as indicated below, where records within the collision chain are read until a key match has been found within the lookup table.
Many lookup tables store large multi-byte keys that are used by processors or processing cores to identify records stored within lookup tables and to access the information stored within those records. For example, many EM algorithms and methods currently exist to identify and access records within a lookup table of “n” records (e.g., R1, R2, . . . Rn) where each record (e.g., R1) includes “m” different fields or data items (e.g., R1-1, R1-2, . . . R1-m) and where one field or data item within each “i” record (e.g., Ri-1) is equal to a unique value called the key. For many EM algorithms, the size of this key may be large, such as tens to hundreds of bytes, and the size of keys within the lookup table may be variable such that the key size can be different for each record. For example, with respect to packet processing systems, the key can include data based upon one or more fields within the packet and can include data defining the length of the key itself (e.g., key size is equal to length field plus data).
As indicated above, some EM algorithms and related lookup tables use table index values generated from the keys, for example by applying a hash function to the keys, to determine memory locations for data records within the lookup tables. The key and the context data are stored for each record using the table index generated from the key, and the table index is used subsequently to locate the record. It is possible, however, for the table index values for different keys to be identical thereby cause index or hash collisions. As such, EM algorithms often identify records having a particular table index value and then search those records to match the key associated with the access request. The large size and variability of the keys, however, can be difficult to manage by applications operating as part of the processing system. Further, there are no fixed keys associated with each record that can be used to management purposes by the processing system.